训练指南 网络流题集

Diposting di | Edited on

A.UVA - 11248 (最大流，最小割)

UVA - 11248 Frequency Hopping

题意

给定一个有向网络，每条边均有一个容量。问是否存在一个从点1到点N，流量为C的流。如果不存在，是否可以恰好修改一条弧的容量，使得存在这样的流。

思路

先求一遍最大流，如果大于等于C，那么就直接输出possible。

否则的话就是最大流达不到C，那么对哪些边进行扩容呢，肯定是选择最小割！

将最小割的边集全部求出来，之后每条边都尝试将容量变为C，看看能否达到要求。

优化一：求完最大流后把流量留着，以后每次在它的基础上增广。

优化二：每次没必要求出最大流，增广到流量至少为C时就可以停下来。

搞不到为什么刘汝佳代码那么快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Edge{
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f)
    :from(u),to(v),cap(c),flow(f){}
    bool operator<(const Edge& a)const{
        return from<a.from||(from==a.from&&to<a.to);
    }
};
struct Dinic{
    int n,m,s,t;
    vector<Edge>edges;
    vector<int>G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];
    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void ClearFlow(){
        for(int i=0;i<edges.size();i++)edges[i].flow=0;
    }
    void AddEdge(int from,int to,int cap){
        edges.push_back(Edge(from,to,cap,0));
        edges.push_back(Edge(to,from,0,0));
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    bool BFS(){
        memset(vis,0,sizeof(vis));
        memset(d,0,sizeof(d));
        queue<int>q;
        q.push(s);
        d[s]=0;
        vis[s]=1;
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int i=0;i<G[x].size();i++){
                Edge& e=edges[G[x][i]];
                if(!vis[e.to]&&e.cap>e.flow){
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a){
        if(x==t||a==0)return a;
        int flow=0,f;
        for(int &i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(a==0)break;
            }
        }
        return flow;
    }
    int Maxflow(int s,int t){
        this->s=s;this->t=t;
        int flow=0;
        while(BFS()){
            memset(cur,0,sizeof(cur));
            flow+=DFS(s,inf);
        }
        return flow;
    }
    vector<int>Mincut(){ /// call this after maxflow
        vector<int>ans;
        for(int i=0;i<edges.size();i++){
            Edge& e=edges[i];
            if(vis[e.from]&&!vis[e.to]&&e.cap>0)ans.push_back(i);
        }
        return ans;
    }
    void Reduce(){
        for(int i=0;i<edges.size();i++)edges[i].cap-=edges[i].flow;
    }
}g;

int main()
{
    int n,e,c,kase=0;
    while(scanf("%d%d%d",&n,&e,&c)==3&&n){
        g.init(n);
        while(e--){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            g.AddEdge(a-1,b-1,c);
        }
        int flow=g.Maxflow(0,n-1);
        printf("Case %d: ",++kase);
        if(flow>=c)printf("possible\n");
        else{
            vector<int>cut=g.Mincut();
            g.Reduce();
            vector<Edge>ans;
            for(int i=0;i<cut.size();i++){
                Edge& e=g.edges[cut[i]];
                e.cap=c;
                g.ClearFlow();
                if(flow+g.Maxflow(0,n-1)>=c)ans.push_back(e);
                e.cap=0;
            }
            if(ans.empty())printf("not possible\n");
            else{
                sort(ans.begin(),ans.end());
                printf("possible option:(%d,%d)", ans[0].from+1, ans[0].to+1);
                for(int i = 1; i < ans.size(); i++)
                printf(",(%d,%d)", ans[i].from+1, ans[i].to+1);
                printf("\n");
            }
        }
    }
    return 0;
}

B.UVALive - 2531 （构图最大流）

题意

有 n 个队伍进行比赛，每个队伍比赛数目是一样的，每场恰好一个胜一个负，给定每个队伍当前胜的场数败的数目，以及两个队伍剩下的比赛场数，问你冠军队伍可能是哪些队。

思路

对每个队伍 i 进行判断是不是能冠军，最优的情况的就是剩下的比赛全都胜，也就是一共胜的数目就是剩下的要比赛的数再加上原来胜的数目sum，然后把每两个队伍比赛看成一个结点，(u, v)，然后从 s 向 结点加一条容量要打的比赛数目的容量，然后从 (u, v) 向 u 和 v 分别加一条容量为无穷大的边，然后每个 u 向 t 加一条容量为 sum - w[i] ，跑一个最大流，如果是满流是，那么就是有解，也就是 i 可能是冠军。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=700+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Edge{
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f)
    :from(u),to(v),cap(c),flow(f){}
    bool operator<(const Edge& a)const{
        return from<a.from||(from==a.from&&to<a.to);
    }
};
struct Dinic{
    int n,m,s,t;
    vector<Edge>edges;
    vector<int>G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];
    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int cap){
        edges.push_back(Edge(from,to,cap,0));
        edges.push_back(Edge(to,from,0,0));
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    bool BFS(){
        memset(vis,0,sizeof(vis));
        memset(d,0,sizeof(d));
        queue<int>q;
        q.push(s);
        d[s]=0;
        vis[s]=1;
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int i=0;i<G[x].size();i++){
                Edge& e=edges[G[x][i]];
                if(!vis[e.to]&&e.cap>e.flow){
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a){
        if(x==t||a==0)return a;
        int flow=0,f;
        for(int &i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(a==0)break;
            }
        }
        return flow;
    }
    int Maxflow(int s,int t){
        this->s=s;this->t=t;
        int flow=0;
        while(BFS()){
            memset(cur,0,sizeof(cur));
            flow+=DFS(s,inf);
        }
        return flow;
    }
}g;
const int maxt=25+5;
int n,w[maxt],d[maxt],a[maxt][maxt];
inline int ID(int u,int v){return u*n+v+1;}
inline int ID(int u){return n*n+u+1;}
bool canWin(int team){
    int total=w[team];
    for(int i=0;i<n;i++)total+=a[team][i];
    for(int i=0;i<n;i++)
        if(w[i]>total)return false;
    g.init(n*n+n+2);
    int full=0;
    int s=0,t=n*n+n+1;
    for(int u=0;u<n;u++){
        for(int v=u+1;v<n;v++){
            if(a[u][v]>0)g.AddEdge(s,ID(u,v),a[u][v]);
            full+=a[u][v];
            g.AddEdge(ID(u,v),ID(u),inf);
            g.AddEdge(ID(u,v),ID(v),inf);
        }
        if(w[u]<total)g.AddEdge(ID(u),t,total-w[u]);
    }
    return g.Maxflow(s,t)==full;
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++)cin>>w[i]>>d[i];
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)cin>>a[i][j];
        bool first=true;
        for(int i=0;i<n;i++)
        if(canWin(i)){
            if(first)first=false;else cout<<" ";
            cout<<i+1;
        }
        cout<<endl;
    }
    return 0;
}

C.UVA - 10779 (构图最大流)

题意

Bob与他的朋友交换贴纸;他的这些朋友只交换自己没有的贴纸;且用的是自己所有的重复贴纸;现在要求Bob最大能得到多少张贴纸; （Bob可以不只用重复的贴纸）

思路

把人和物品都进行编号,添加原点s和汇点e,s到每个物品连边容量为Bob拥有的数目;所有物品向汇点e连边容量为1;

如果一个人向他拥有的物品连边,容量为数目减1,表示他自己会留一个;如果他不拥有某件物品,则物品向这个人连一条边,表示这个人最多接受一件这个物品;

然后跑一遍最大流就是答案了;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=700+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Edge{
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f)
    :from(u),to(v),cap(c),flow(f){}
    bool operator<(const Edge& a)const{
        return from<a.from||(from==a.from&&to<a.to);
    }
};
struct Dinic{
    int n,m,s,t;
    vector<Edge>edges;
    vector<int>G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];
    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int cap){
        edges.push_back(Edge(from,to,cap,0));
        edges.push_back(Edge(to,from,0,0));
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    bool BFS(){
        memset(vis,0,sizeof(vis));
        memset(d,0,sizeof(d));
        queue<int>q;
        q.push(s);
        d[s]=0;
        vis[s]=1;
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int i=0;i<G[x].size();i++){
                Edge& e=edges[G[x][i]];
                if(!vis[e.to]&&e.cap>e.flow){
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a){
        if(x==t||a==0)return a;
        int flow=0,f;
        for(int &i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(a==0)break;
            }
        }
        return flow;
    }
    int Maxflow(int s,int t){
        this->s=s;this->t=t;
        int flow=0;
        while(BFS()){
            memset(cur,0,sizeof(cur));
            flow+=DFS(s,inf);
        }
        return flow;
    }
}g;
const int maxt=30+5;
int n,w[maxt],d[maxt],a[maxt][maxt],m;
inline int ID(int u){return u;}///物品
inline int PID(int u){return m+u;}
int S,T;
void build(){
    for(int i=1;i<=m;i++){
        if(a[1][i])
            g.AddEdge(S,i,a[1][i]);
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]>=2){
                g.AddEdge(PID(i),ID(j),a[i][j]-1);
            }
            else if(!a[i][j]){
                g.AddEdge(ID(j),PID(i),1);
            }
        }
    }
    for(int i=1;i<=m;i++){
        g.AddEdge(ID(i),T,1);
    }
}
int main()
{
    int t;
    int cast=1;
    cin>>t;
    while(t--){
        cin>>n>>m;
        g.init(n+m+2);
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++){
            int tot;cin>>tot;
            while(tot--){
                int aa;
                cin>>aa;
                a[i][aa]++;
            }
        }
        S=0,T=n+m+1;
        build();
        cout<<"Case #"<<cast++<<": ";
        cout<<g.Maxflow(S,T)<<endl;
    }
    return 0;
}

D.UVA - 11613 (最大费用流)

题意

A公司生产一种元素，给出该元素在未来M个月中每个月的单位售价，最大生产量，生产成本，最大销售量和最大存储时间，和每月存储代价，问这家公司在M个月内所能赚大的最大利润

思路

建边的时候，费用我用的是相反数，所以得到最小费用后要去相反数
MCMF的时候，用一个数组纪录了到达汇点时所花费的最小价值，因为取的是相反数，所以当价值为正时，就表示已经亏本了，所以可以退出了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=700+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Edge{
    int from,to,cap,flow,cost;
    Edge(int u,int v,int c,int f,int w)
    :from(u),to(v),cap(c),flow(f),cost(w){}
};
struct MCMF{
    int n,m;
    vector<Edge>edges;
    vector<int>G[maxn];
    int inq[maxn];
    int d[maxn];
    int p[maxn];
    int a[maxn];
    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int cap,int cost){
        edges.emplace_back(from,to,cap,0,cost);
        edges.emplace_back(to,from,0,0,-cost);
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    bool BellmanFord(int s,int t,int& flow,ll& cost){
        for(int i=0;i<n;i++)d[i]=inf;
        memset(inq,0,sizeof(inq));
        d[s]=0;
        inq[s]=1;
        p[s]=0;
        a[s]=inf;
        queue<int>q;
        q.push(s);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            inq[u]=0;
            for(int i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
                    d[e.to]=d[u]+e.cost;
                    p[e.to]=G[u][i];
                    a[e.to]=min(a[u],e.cap-e.flow);
                    if(!inq[e.to]){
                        q.push(e.to);
                        inq[e.to]=1;
                    }
                }
            }
        }
        if(d[t]>0)return false;
        flow+=a[t];
        cost+=(ll)d[t]*(ll)a[t];
        for(int u=t;u!=s;u=edges[p[u]].from){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        return true;
    }
    int MincostMaxflow(int s,int t,ll& cost){
        int flow=0;
        cost=0;
        while(BellmanFord(s,t,flow,cost));
        return flow;
    }
}g;

int main()
{
    int t;
    int cast=1;
    cin>>t;
    int month,st_cost;
    while(t--){
        cin>>month>>st_cost;
        g.init(month*2+2);
        int source=0,sink=2*month+1;
        for(int i=1;i<=month;i++){
            int make_cost,make_limit,price,sell_limit,max_store;
            cin>>make_cost>>make_limit>>price>>sell_limit>>max_store;
            g.AddEdge(source,i,make_limit,make_cost);
            g.AddEdge(month+i,sink,sell_limit,-price);
            for(int j=0;j<=max_store;j++){
                if(i+j<=month)
                    g.AddEdge(i,month+i+j,inf,st_cost*j);
            }
        }
        ll cost=0;g.MincostMaxflow(source,sink,cost);
        cout<<"Case "<<cast++<<": "<<-cost<<endl;
    }
    return 0;
}